from typing import *
from bisect import bisect_left


class Solution:

    def minCapability(self, nums: List[int], k: int) -> int:

        def f(x):
            b = False
            c = 0
            for num in nums:
                if num <= x and not b:
                    c += 1
                    b = True
                else:
                    b = False
            return c

        return bisect_left(range(max(nums)), k, key=f)


class Solution:

    def minCapability(self, nums: List[int], k: int) -> int:

        def f(x):
            a = b = 0

            for num in nums:
                if num <= x:
                    a, b = b, max(a + 1, b)
                else:
                    a = b
            return b

        return bisect_left(range(max(nums)), k, key=f)


s = Solution()
print(s.minCapability([2, 3, 5, 9], 2) == 5)
print(s.minCapability([2, 7, 9, 3, 1], 2) == 2)
